1. Field of the Invention
The present invention is directed to computer systems. More particularly, it is directed to image processing.
2. Description of the Related Art
Image processing often involves the performance of various filtering operations on image data using one or more convolution operations. For example, box filters are typically implemented using a series of convolution steps performed across the rows and columns of an image. These convolutions may involve large numbers of operations on subsets of the input image data, and are often implemented by applying a kernel of support over the image in a sliding window. Different techniques for speeding up convolutions on image data have been developed, but may not be suitable for certain operations.
One example of a technique for speeding up convolutions is a prior art technique for fast box filters that involves the use of running histograms. Pyramidal data-structures have also been used in the past to accelerate various image processing algorithms. MIP maps, for instance, are sometimes used to store a filtered pyramid of a base image. Such pyramids are typically used when approximating a linear additive rectangular filter by finding a corresponding level of the pyramid and interpolating entries. MIP maps, which are constructed using down sampling, may be pre-computed and used in future convolutions. However, the results of these convolutions are not as accurate as the results of convolutions performed on original or exact image data.
Another prior art technique for speeding up convolutions involves summed-linear tables, where an exact additive convolution can be computed over a one-dimensional array of pixels using two table look-ups. This approach is extended in two dimensions to summed-area tables, where, with four table look-ups, the rectangular convolution may be computed. However, convolutions using linear sum tables lack numerical precision because a linear sum table stores the indefinite integral to the left of each pixel. The finite integral is then computed using the difference between two indefinite integrals. This can lead to the computation of small differences between large numbers. For finite precision floating point systems, this can lead to quantizing errors in some portions of the image, and is especially apparent for summed-area tables in two dimensions.
The prior art techniques described above may not be suitable for fast convolutions of certain filtering operations. For example, max filters have historically required either explicit convolution or the building of binary trees on the fly, both of which may be slow and may not be sped up using the techniques described above.